/*
提交链接:https://leetcode.cn/problems/find-k-pairs-with-smallest-sums/description/
373. 查找和最小的 K 对数字
赖德檀 2024/12/19
*/

class Solution {
public:
    vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
        // 定义一个自定义比较器 lambda 表达式，用于优先队列中的元素排序。
        auto cmp = [&nums1, &nums2](const pair<int, int> & a, const pair<int, int> & b) {
            return nums1[a.first] + nums2[a.second] > nums1[b.first] + nums2[b.second];
        };
        int n = nums1.size(); // 获取 nums1 的大小
        int m = nums2.size(); // 获取 nums2 的大小
        vector<vector<int>> arr;   // 存储结果的二维向量
        // 创建一个优先队列，并使用上面定义的比较器进行排序。
        // 队列中的每个元素是一个 pair<int, int>，表示来自 nums1 和 nums2 的索引。
        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> qe(cmp);//自定义大根堆
        // 将nums1的前 min(k, n) 个元素与nums2的第一个元素组合加入优先队列。
        for (int i = 0; i < min(k, n); i++) {
            qe.emplace(i, 0);
        }

        // 开始从优先队列中提取最小的数对，直到提取了 k 个数对或队列为空。
        while (k--&&!qe.empty()) {
            auto [x, y] = qe.top(); 
            qe.pop(); // 移除队列顶部的元素
            // 将当前最小的数对添加到结果集中。
            arr.push_back({nums1[x], nums2[y]});
            // 如果不是最后一列，则将同一行的下一个可能的数对加入队列。
            if (y+1<m) {
                qe.emplace(x, y + 1);//添加(1,0),(0,1)上面添加了
                //添加了(0,0),接下来就要判断(0,1)和(1,0)谁大
            }
        }
        return arr;
    }
};

